package com.chj.dfs.class04;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;

public class Code21_CourseSchedule {

	public static class Edge {
		public int weight;
		public Node from;
		public Node to;

		public Edge(int weight, Node from, Node to) {
			this.weight = weight;
			this.from = from;
			this.to = to;
		}
	}

	public static class Node {
		public int value;
		public int in;
		public int out;
		public ArrayList<Node> nexts;
		public ArrayList<Edge> edges;

		public Node(int value) {
			this.value = value;
			in = 0;
			out = 0;
			nexts = new ArrayList<>();
			edges = new ArrayList<>();
		}
	}

	public static class Graph {
		public HashMap<Integer, Node> nodes;
		public HashSet<Edge> edges;

		public Graph() {
			nodes = new HashMap<>();
			edges = new HashSet<>();
		}
	}

	public static Graph createGraph(int[][] matrix) {
		Graph graph = new Graph();
		for (int i = 0; i < matrix.length; i++) { // matrix[0][0], matrix[0][1] matrix[0][2]
			Integer from = matrix[i][0];
			Integer to = matrix[i][1];
			Integer weight = matrix[i][2];

			if (!graph.nodes.containsKey(from)) {
				graph.nodes.put(from, new Node(from));
			}

			if (!graph.nodes.containsKey(to)) {
				graph.nodes.put(to, new Node(to));
			}

			Node fromNode = graph.nodes.get(from);
			Node toNode = graph.nodes.get(to);

			Edge newEdge = new Edge(weight, fromNode, toNode);
			fromNode.nexts.add(toNode);
			fromNode.out++;
			toNode.in++;
			fromNode.edges.add(newEdge);
			graph.edges.add(newEdge);
		}

		return graph;
	}

	public static boolean canFinish(int numCourses, int[][] prerequisites) {
		int[][] matrix = new int[prerequisites.length][3];

		// 创建图，链接图的顶点
		for (int i = 0; i < prerequisites.length; i++) {
			int from = prerequisites[i][1];
			int to = prerequisites[i][0];
			int weight = 0;

			int[] temp = new int[3];
			temp[0] = from;
			temp[1] = to;
			temp[2] = weight;

			matrix[i] = temp;
		}

		Graph graph = createGraph(matrix);

		// key：某一个node
		// value：剩余的入度
		HashMap<Node, Integer> inMap = new HashMap<>();
		// 入度为0的点，才能进这个队列
		Deque<Node> Q = new ArrayDeque<>();
		for (Node node : graph.nodes.values()) {
			inMap.put(node, node.in);
			if (node.in == 0) {
				Q.addLast(node);
			}
		}

		// 宽搜
		while (!Q.isEmpty()) {
			Node cur = Q.pollFirst();
			for (Node next : cur.nexts) {
				inMap.put(next, inMap.get(next) - 1);
				if (inMap.get(next) == 0) {
					Q.addLast(next);
				}
			}
		}

		for (Node node : graph.nodes.values()) {
			if (inMap.get(node) != 0) {
				return false;
			}
		}

		return true;
	}

//	[[0, 1, 0], [0, 2, 0], [1, 3, 0], [2, 3, 0], [0, 0, 0]
	public static void main(String[] args) {
		{
			int numCourses = 4;
			int[][] prerequisites = new int[][] { { 1, 0 }, { 2, 0 }, { 3, 1 }, { 3, 2 } };
			System.out.println(canFinish(numCourses, prerequisites));
		}

		{
			int numCourses = 2;
			int[][] prerequisites = new int[][] { { 1, 0 } };
			System.out.println(canFinish(numCourses, prerequisites));
		}
	}
}
